//
// Description: 198. 打家劫舍
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>

using namespace std;

int rob(vector<int> &nums) {
    int n = nums.size();
    if (n == 1) {
        return nums[0];
    }
    // dp[i] 表示到 i 位置时，偷窃的最高金额
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        // 偷窃 i 位置时，不能偷窃 i - 1 位置，最大值为 dp[i - 2] + nums[i];
        // 不偷窃 i 位置时，最大值为 dp[i - 1]
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }

    return dp[n - 1];
}

int main() {
    vector<int> nums{2, 7, 9, 3, 1};
    auto res = rob(nums);
    cout << res << endl;

    return 0;
}